# -*- coding: utf-8 -*-

"""python内置的了堆数据结构<heapq>，为小顶堆，且在数组中下标始于0。在此，实现一个大顶堆。
堆能解决问题的核心思想：
1）顶点是这个堆中数据的上限或下限：优先级队列，高性能任务定时器；
2）堆的容量：top K问题，中位数<大小堆>，99%响应时间问题<大小堆>"""


class Heap():
    def __init__(self, li, capacity=float('infinity')):
        self.head = li
        self.capacity = capacity
        self.length = 0

        self.__build()
    
    def __build(self):
        def jiandui(i):
            if i <= 0:
                return
            jiandui(i-1)
            self.__heapify(i)

        length = len(self.head)
        if length > self.capacity:
            jiandui(self.capacity-1)
            self.length = self.capacity

            j = length-1
            while True:
                if j < self.capacity:
                    break
                self.push(self.head[j])
                self.head.pop()
                j -= 1
        else:
            jiandui(length-1)
            self.length = length

    def __heapify(self, i):
        if i == 0:
            return
        parent = (i+1)//2-1
        if self.head[parent] < self.head[i]:
            self.head[parent], self.head[i] = self.head[i], self.head[parent]
            self.__heapify(parent)

    def __top_heapify(self, i):
        left, right = i*2+1, i*2+2
        if left >= self.length-1:
            return
        if self.head[i] >= self.head[left] and self.head[i] >= self.head[right]:
            return
        elif self.head[left] >= self.head[i] and self.head[left] >= self.head[right]:
            self.head[left], self.head[i] = self.head[i], self.head[left]
            self.__top_heapify(left)
        elif self.head[right] >= self.head[i] and self.head[right] >= self.head[left]:
            self.head[right], self.head[i] = self.head[i], self.head[right]
            self.__top_heapify(right)

    def push(self, item):
        if self.length < self.capacity:
            self.head.append(item)
            self.__heapify(self.length)
            self.length += 1
        elif item < self.head[0]:
            self.head[0] = item
            self.__top_heapify(0)

    def pop(self):
        rs = self.head[0]
        tail = self.head[-1]
        
        self.head.pop()
        self.length -= 1

        self.head[0] = tail
        self.__top_heapify(0)
        return rs

    def pushpop(self, item):
        """push -> pop"""
        if item >= self.head[0]:
            return item
        elif item < self.head[0]:
            rs = self.head[0]
            self.head[0] = item
            self.__top_heapify(0)
            return rs

    def replace(self, item):
        """pop -> push"""
        rs = self.head[0]
        self.head[0] = item
        self.__top_heapify(0)
        return rs


if __name__ == '__main__':
    li = [0,1,2,3,4,5,6,7,8,8]
    heap = Heap(li, 6)
    print(heap.head)
    heap.push(3)
    print(heap.head)
    heap.pop()
    print(heap.head)
    heap.replace(-1)
    print(heap.head)

